#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int TreeDataType;
typedef struct Tree
{
	TreeDataType val;
	struct Tree* left;
	struct Tree* right;
}Tree;

Tree* TreeNode(TreeDataType x)
{
	Tree* newnode = (Tree*)malloc(sizeof(Tree));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;
	newnode->left = newnode->right = NULL;

	return newnode;
}

Tree* CreateTree()
{
	Tree* n1 = TreeNode(1);
	Tree* n2 = TreeNode(2);
	Tree* n3 = TreeNode(3);
	Tree* n4 = TreeNode(4);
	Tree* n5 = TreeNode(5);
	Tree* n6 = TreeNode(6);

	n1->left = n2;
	n2->left = n3;
	n1->right = n4;
	n4->left = n5;
	n4->right = n6;

	return n1;
}

void PreOrder(Tree* gen)
{
	if (gen == NULL)
	{
		return;
	}

	printf("%d ", gen->val);
	PreOrder(gen->left);
	PreOrder(gen->right);
}

void InOrder(Tree* gen)
{
	if (gen == NULL)
	{
		return;
	}

	InOrder(gen->left);
	printf("%d ", gen->val);
	InOrder(gen->right);
}

void PostOrder(Tree* gen)
{
	if (gen == NULL)
	{
		return;
	}

	PostOrder(gen->left);
	PostOrder(gen->right);
	printf("%d ", gen->val);
}

int TreeSize(Tree* gen)
{
	return (gen == NULL) ? 0 : 
		1 + TreeSize(gen->left) + TreeSize(gen->right);
}

int TreeHeight(Tree* gen)
{
	if (gen == NULL)
		return 0;
	int leftDepth = TreeHeight(gen->left);
	int rightDepth = TreeHeight(gen->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

int TreeKSize(Tree* gen, int k)
{
	assert(k > 0);
	if (gen == NULL)
		return 0;
	if (k == 1)
		return 1;
	return TreeKSize(gen->left, k - 1) + TreeKSize(gen->right, k - 1);
}

Tree* TreeFind(Tree* gen, int val)
{
	if (gen == NULL)
		return NULL;
	if (gen->val == val)
		return gen;
	Tree* ret1 = TreeFind(gen->left, val);
	if (ret1)
		return ret1;
	return TreeFind(gen->right, val);
}

int main()
{
	Tree* gen = CreateTree();
	PreOrder(gen);
	printf("\n");
	InOrder(gen);
	printf("\n");
	PostOrder(gen);
	printf("\n");
	printf("%d\n", TreeSize(gen));
	printf("%d\n", TreeHeight(gen));
	printf("%d\n", TreeKSize(gen, 2));
	printf("%p\n", TreeFind(gen, 5));


	return 0;
}